|
|
Syntaktická analýza založená na stavových gramatikách
Paulík, Miroslav ; Solár, Peter (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce popisuje vlastnosti stavových gramatik a n-limitovaných stavových gramatik s důrazem na nedeterminismus v analýze takových gramatik. Zejména se zaměřuje na problémy způsobené povolením vymazávacích pravidel a možných výskytů rekurze. Na základě analýzy těchto problémů nabízí možná řešení, která jsou posléze uplatněna při návrhu prakticky zaměřené metody paralelní syntaktické analýzy. Tato metoda je výrazně rychlejší, než sekvenční analýza s návratem.
|
|
|
Knihovna operací nad konečnými automaty
Bartůněk, Petr ; Puš, Viktor (oponent) ; Kaštil, Jan (vedoucí práce)
Tato práce se zabývá dvěma základními operacemi nad konečnými automaty. Determinizací nedeterministických konečných automatů a minimalizací deterministických konečných automatů. Pro obě tyto operace jsem navrhoval sekvenční algoritmy, které jsou paralelizovatelné. Zabývám se hledáním zrychlení především pomocí SSE instrukcí nebo pomocí knihovny openMP. Trendem dnešní doby je především zvyšování počtu procesorů, proto budu navrhovat paralelní algoritmy pro více procesorů. Při hledání optimálního řešení budu zkoumat další možnosti, jak dosáhnout zrychlení, např. efektivním uložením datových struktur v paměti.
|
|
|
Simulace konečných převodníků
Micenková, Barbora ; Kolář, Dušan (oponent) ; Lukáš, Roman (vedoucí práce)
K rychlému překladu mezi strojovým kódem a assemblerem za účelem simulace je možné použít speciální abstraktní model - tzv. párový konečný automat. Jeho vnitřní uspořádání nás přivádí k problematice konečných převodníků. Vzhledem k tomu, že simulace deterministických převodníků je efektivnější, musíme se procesem determinizace zabývat. Existující algoritmy jsou bohužel aplikovatelné pouze na převodníky provádějící překlad konečných jazyků, zatímco my na vstupu očekáváme obecně nekonečný jazyk. Proto je nutné nalézt způsob, jak rychle rozpoznat, je-li převodník na vstupu determinizovatelný. V této bakalářské práci jsou shrnuty doposud publikované poznatky z oblasti determinizace konečných převodníků a rovněž navržen nový algoritmus determinizace převodníků provádějících překlad obecně nekonečných jazyků. Nedeterminizovatelné převodníky na vstupu jsou detekovány.
|
|
|
Multidimensionální jazyky a jejich automaty
Dibďák, Lukáš ; Martiško, Jakub (oponent) ; Meduna, Alexandr (vedoucí práce)
Práce seznamuje s teorií formálních jazyků a konečných automatů. Popisuje zobecnění této teorie do dvou rozměrů. Představuje základní typy dvoudimensionálních automatů, přede- vším teselační automaty. Pro teselační automaty jsou nabídnuty algoritmy k jejich determinizaci. Jeden z algoritmů je následně používán přiloženou aplikací pro determinizaci.
|
|
|
Multidimensionální jazyky a jejich automaty
Dibďák, Lukáš ; Martiško, Jakub (oponent) ; Meduna, Alexandr (vedoucí práce)
Práce seznamuje s teorií formálních jazyků a konečných automatů. Popisuje zobecnění této teorie do dvou rozměrů. Představuje základní typy dvoudimensionálních automatů, přede- vším teselační automaty. Pro teselační automaty jsou nabídnuty algoritmy k jejich determinizaci. Jeden z algoritmů je následně používán přiloženou aplikací pro determinizaci.
|
|
|
Simulace konečných převodníků
Micenková, Barbora ; Kolář, Dušan (oponent) ; Lukáš, Roman (vedoucí práce)
K rychlému překladu mezi strojovým kódem a assemblerem za účelem simulace je možné použít speciální abstraktní model - tzv. párový konečný automat. Jeho vnitřní uspořádání nás přivádí k problematice konečných převodníků. Vzhledem k tomu, že simulace deterministických převodníků je efektivnější, musíme se procesem determinizace zabývat. Existující algoritmy jsou bohužel aplikovatelné pouze na převodníky provádějící překlad konečných jazyků, zatímco my na vstupu očekáváme obecně nekonečný jazyk. Proto je nutné nalézt způsob, jak rychle rozpoznat, je-li převodník na vstupu determinizovatelný. V této bakalářské práci jsou shrnuty doposud publikované poznatky z oblasti determinizace konečných převodníků a rovněž navržen nový algoritmus determinizace převodníků provádějících překlad obecně nekonečných jazyků. Nedeterminizovatelné převodníky na vstupu jsou detekovány.
|
|
|
Syntaktická analýza založená na stavových gramatikách
Paulík, Miroslav ; Solár, Peter (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce popisuje vlastnosti stavových gramatik a n-limitovaných stavových gramatik s důrazem na nedeterminismus v analýze takových gramatik. Zejména se zaměřuje na problémy způsobené povolením vymazávacích pravidel a možných výskytů rekurze. Na základě analýzy těchto problémů nabízí možná řešení, která jsou posléze uplatněna při návrhu prakticky zaměřené metody paralelní syntaktické analýzy. Tato metoda je výrazně rychlejší, než sekvenční analýza s návratem.
|
|
|
Knihovna operací nad konečnými automaty
Bartůněk, Petr ; Puš, Viktor (oponent) ; Kaštil, Jan (vedoucí práce)
Tato práce se zabývá dvěma základními operacemi nad konečnými automaty. Determinizací nedeterministických konečných automatů a minimalizací deterministických konečných automatů. Pro obě tyto operace jsem navrhoval sekvenční algoritmy, které jsou paralelizovatelné. Zabývám se hledáním zrychlení především pomocí SSE instrukcí nebo pomocí knihovny openMP. Trendem dnešní doby je především zvyšování počtu procesorů, proto budu navrhovat paralelní algoritmy pro více procesorů. Při hledání optimálního řešení budu zkoumat další možnosti, jak dosáhnout zrychlení, např. efektivním uložením datových struktur v paměti.
|
host ::
RSS.